package SelectSort;/*
 *
 *@author:    Xavier
 *@data:      2023 - 08 - 26
 *@time:      20:54
 *
 */

import java.util.Arrays;

//选择排序
//中心思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，
// 存放在序列的起始位置，直到全部待排序的数据元素排完 。

/*
* 时间复杂度：O(N^2)
* 空间复杂度：O(1)
* 稳定性：不稳定的排序
* */
public class SelectionSort {
    public static void selectSort1(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int min = arr[i];
            int minIndex = i;
            for (int j = i+1 ; j < arr.length; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            int tmp = arr[i];
            arr[i] = min;
            arr[minIndex] = tmp;
        }
    }

    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i+1 ; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr, minIndex, i);
        }
    }

    public static void selectSort2(int[] arr){
        int left = 0;
        int right = arr.length-1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <= right; i++) {
                if (arr[i] < arr[minIndex]) {
                    minIndex = i;
                }
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(arr,minIndex,left);
            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(arr,maxIndex,right);
            left++;
            right--;
        }
    }

    private static void swap(int[] arr, int i , int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr1 = {2,8,7,3,9,5,9,0,0,2};
        int[] arr = {10,2,8,7,3,9,5,9,0,0,2};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));


    }
}
